package com.example.demo.listnode;

import com.example.demo.model.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 返回链表开始入环的第一个节点
 */
public class DetectCycle {

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        while (true) {
            if (fast == null || fast.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) break;
        }

        fast = head;

        while (fast != slow) {
            slow = slow.next;
            fast = fast.next;
        }

        return fast;
    }

    public ListNode detectCycle2(ListNode head) {
        if (head == null) return null;

        Set<ListNode> set = new HashSet<>();
        set.add(head);

        while (head != null) {
            head = head.next;

            if (set.contains(head)) {
                return head;
            }

            set.add(head);
        }

        return null;
    }
}
